package com.sunny.leetcode.链表;

/**
 * 反转一个单链表。
 *
 * 示例:
 *  输入: 1->2->3->4->5->NULL
 *  输出: 5->4->3->2->1->NULL
 *
 * 进阶:
 *  你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/reverse-linked-list
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author Sunny
 * @date 2020/7/4
 */
public class _206_反转链表 {

    /**
     * 采用递归方式
     *
     * @param head 头节点
     * @author Sunny
     * @date 2020/7/4
     */
    public ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode newHead = reverseList1(head.next);
        head.next.next = head;
        head.next = null;

        return newHead;
    }

    /**
     * 采用非递归方式
     *
     * @param head 头节点
     * @author Sunny
     * @date 2020/7/4
     */
    public ListNode reverseList2(ListNode head) {
        ListNode newHead = null;
        ListNode next = null;
        ListNode curr = head;
        while (curr != null) {
            next = curr.next;
            curr.next = newHead;
            newHead = curr;
            curr = next;
        }
        return newHead;
    }
}
